package feibonaqieArray;

import java.util.Scanner;

public class test1 {
    public static void main(String[] args) {
        /*
         * 斐波那契数列非递归写法
         * */
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long num1 = 1, num2 = 2, result = 0;
        long start1, start2, end1 = 0, end2 = 0;
        start1 = System.currentTimeMillis();
        if (n == 1) {
            result = 1;
        }
        if (n == 2) {
            result = 2;
        }
        for (int i = 3; i <= n; i++) {
            result = num1 + num2;
            num1 = num2;
            num2 = result;
        }
        end1 = System.currentTimeMillis();

        System.out.println(n + "次后非递归结果为：" + result + ",所用时间为：" + (end1 - start1) / 1000);
        start2 = System.currentTimeMillis();
        result = test(n);
        end2 = System.currentTimeMillis();
        System.out.println(n + "次后递归结果为：" + result + ",所用时间为：" + (end2 - start2) / 1000);
    }

    //斐波那契数列递归写法
    public static long test(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return test(n - 1) + test(n - 2);
    }
}